package com.lanqiao.recursionAndRecursion;

/*
*   题目描述
    将整数 n 分成 k份，且每份不能为空，任意两份不能相同(不考虑顺
    序)。
    例如:n-7，k=3，下面三种分法被认为是相同的。
    1,1,5;1,5，1;5，1,1;
    问有多少种不同的分法。
* */


import java.util.Scanner;

/**
 * @author kjx
 */


//这并不是一道很简单的题。他的递归规律是很难找的，这里有一种快一点的方法就是dfs直接暴力搜索，但是dfs我还没细学所以这道题是看了详解后发表自己的看法
//这里先挖坑，学了dfs回来重做这道题

//回到递归本身，找到递归的规律要有一个入口，规律不仅仅一种，首先要进行破局，我们就拿 1 进行来破局：
    /*
    * 第一种来源（对应divide_count(n - 1, k - 1)部分）：
    我们可以先拿出一个1作为单独的一份，那么剩下的任务就是把n - 1分成k - 1份了，
    * 例如对于n = 7，k = 3，我们先确定一份是1，那接下来就是把6分成2份的问题了，而把6分成2份的分法数量可以通过递归调用divide_count(6, 2)
    * 也就是divide_count(n - 1, k - 1)来获取。
    *
    第二种来源（对应divide_count(n - k, k)部分）：
    我们可以先让每一份都先有个基础值1，也就是相当于从n中先减去k（因为有k份，每份先给1）
    * 然后再去分配剩下的数，还是分成k份。例如对于n = 7，k = 3，先给每份都放个1，就用掉了3，还剩下4，接下来就是把4再分配到这3份中的分法数量了，
    * 通过递归调用divide_count(4, 3)也就是divide_count(n - k, k)来获取。
    * */

//说人话就是，一种是 1 单独拿出来，一种是 1 不能单独拿出来
//单独拿出来的规律很好找就是 f(n-1,m-1)就行，关键是 1 不能单独拿出来怎么表达？
//比如7分3,3份中不能出现单独的1，那么我们直接反着来，我们让每一份都至少为1，在此基础上再去划分，也就是三份从1开始，也就是把剩下的4拿出去划分即可
//这样4划分出来最少也是1，这个1加上原来的1也就是2，这样就彻底规避了1不能单独拿出来的情况

public class PartitionCount {
    public static int divideCount(int n, int k) {
        if (n < k) {
            return 0;
        }
        if (n == k) {
            return 1;
        }
        if (k == 1) {
            return 1;
        }
        return divideCount(n - 1, k - 1) + divideCount(n - k, k);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int result = divideCount(n, k);
        System.out.println(result);
    }
}
